# nums = [1,2,3,1]
# k = 3
# t = 0

# nums = [1,0,1,1]
# k = 1
# t = 2

from sortedcontainers import SortedList
nums = [1,5,9,1,5,9]
k = 2
t = 3
#超时
def containsNearbyAlmostDuplicate(nums, k: int, t: int) -> bool:
    for i in range(len(nums)):
        j=i+1
        while j<len(nums) and j<=i+k:
            if abs(nums[i]-nums[j])<=t:
                return True
            j+=1
    return False
def containsNearbyAlmostDuplicate1(nums, k: int, t: int) -> bool:
    #创建桶
    all_buckets={}
    bucket_size = t + 1  # 桶的大小设成t+1更加方便
    for i in range(len(nums)):
        bucket_num = nums[i] // bucket_size  # 放入哪个桶
        #返回条件
        if bucket_num in all_buckets:  # 桶中已经有元素了
            return True
        all_buckets[bucket_num] = nums[i]  # 把nums[i]放入桶中
        #可能存在前一个桶的元素小于等于t
        if (bucket_num - 1) in all_buckets and abs(all_buckets[bucket_num - 1] - nums[i]) <= t:  # 检查前一个桶
            return True
        #后一个桶的元素小于等于t
        if (bucket_num + 1) in all_buckets and abs(all_buckets[bucket_num + 1] - nums[i]) <= t:  # 检查后一个桶
            return True

        # 如果不构成返回条件，那么当i >= k 的时候就要删除旧桶了，以维持桶中的元素索引跟下一个i+1索引只差不超过k
        if i >= k:
            #删掉最开头的那个桶
            all_buckets.pop(nums[i - k] // bucket_size)
    return False

    pass
print(containsNearbyAlmostDuplicate1(nums,k,t))
